package com.zzg.algorithm.dac;

/**
 * @Author zhengzg
 * @Date 2022-10-08
 * @Version v1.0
 * 分治算法：汉诺塔问题
 */
public class Hanoi {

    public static void main(String[] args) {
        hanoi(5, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔移动
     *
     * @param num 所有盘数
     * @param a   A塔
     * @param b   B塔
     * @param c   C塔
     */
    public static void hanoi(int num, char a, char b, char c) {
        if (num == 1) {
            // 只有一个圆盘
            System.out.println(a + "塔 => " + c + "塔");
        } else {
            /*
             * 问题分解
             * 1.多个盘统一看作两部分，上面盘 + 最下面一个盘
             * 2.先把最上面的所有盘 A -> B
             * 3.把最下面的移动到C
             * 4.把B塔所有盘移动到A
             */
            hanoi(num - 1, a, c, b);
            System.out.println(a + "塔 => " + c + "塔");
            hanoi(num - 1, b, a, c);
        }
    }
}
